package homework;

public class Tree<E extends Comparable<E>> {
    private Node root;
    private int size;

    private class Node {
        E data;
        Node left;
        Node right;

        Node(E e) {
            data = e;
        }

        public boolean addChild(E e) {
            int val = data.compareTo(e);
            if (val == 0) {// 相等不添加
                return false;
            } else if (val > 0) {// 向左边添加
                if (left == null) {
                    left = new Node(e);
                    size++;
                    return true;
                } else {
                    // 向左侧内部递归添加元素
                    return left.addChild(e);
                }
            } else {// 向右边添加
                if (right == null) {
                    right = new Node(e);
                    size++;
                    return true;
                } else {
                    // 向右侧内部递归添加元素
                    return right.addChild(e);
                }
            }
        }

        public void appendTo(StringBuilder buf) {
            //中序排序
            if (left != null) {
                left.appendTo(buf);
            }
            buf.append(data).append(",");
            if (right != null) {
                right.appendTo(buf);
            }
        }
    }

    public boolean add(E e) {
        if (root == null) {
            root = new Node(e);
            size++;
            return true;
        } else {
            return root.addChild(e);
        }
    }

    public String toString() {
        if (root == null) {
            return "[]";
        }
        StringBuilder buf = new StringBuilder("[");
        root.appendTo(buf);
        buf.delete(buf.lastIndexOf(","), buf.length());
        return buf.append("]").toString();
    }

}
